package com.example.demo.tixiban;

/**
 * @author xujm
 * @version V2.4
 *
 *  对于一个数组 arr=[3,4,5,1,2]   求有多少个子数组的和在范围[4,5]
 *
 *  方法一: 暴力求解
 *   先定义一个前缀和数组 preArr:
 *   有了这个数组，我们可以求任意范围内的数组之和，并且保证时间复杂度为O(1)
 *    遍历这个数组的所有子数组，然后根据preArr比较出在范围[4,5]之内子数组
 *     时间复杂度 O(n) * O(n) (由于定于了preArr,否则求和还需要 * O(N))
 *
 *   方法二:归并排序思想解
 *    对于数组 arr=[3,4,5,1,2],得到前缀和数组 preArr
 *    假设对于任意下标 i > 0 ,我们获取到他的前缀和为 X，求范围[4,5]之内的子数组
 *    如果preArr[0] 等于 1
 *    那么  4<= X-preArr[0] <=5 是否成立 ? 如果成立，那么证明 [1,X] 之间存在子数组满足和在[4,5]范围内
 *    那么条件可以转换为:  X-5<= preArr[0] <= X-4 是否成立
 *
 *    套入归并排序: 左边的所有数 总是会和右边的所有数比较，如果满足上述条件，说明存在子数组。
 *     时间复杂度: O(N) * logN
 * @since 2.4.0 2022/3/5 11:34
 */
public class Arr_求一个数组在范围内的集合数量 {

    /**
     *  方法一
     * @param arr
     * @param lower
     * @param uper
     * @return
     */
    public static int getNumFromRange(int [] arr, int lower, int uper){

        int res = 0;
        int [] preArr = new int [arr.length];
        preArr[0] = arr[0];
        for(int i=1;i<preArr.length;i++){
            preArr[i] = preArr[i-1] + arr[i];
        }

        for(int i = 0;i<arr.length;i++){
            for(int j=i;j<arr.length;j++){
                if( i == 0){
                    if(preArr[j] >= lower && preArr[j] <= uper){
                        res++;
                    }
                }else if(preArr[j]-preArr[i-1] >= lower && preArr[j]-preArr[i-1] <= uper) {
                    res++;
                }
            }
        }
        return res;
    }

    /**
     * 方法二
     * @param arr
     * @param lower
     * @param uper
     * @return
     */
    public static int getNumFromRange2(int [] arr, int lower, int uper){
        int [] preArr = new int [arr.length];
        preArr[0] = arr[0];
        for(int i=1;i<preArr.length;i++){
            preArr[i] = preArr[i-1] + arr[i];
        }
        return split(preArr,0,preArr.length-1,lower,uper);
    }


    public static int split(int [] preArr,int i, int j,int lower,int uper){
        if(i == j){ // 归并排序对于单个数字是忽略的，此处判断
            if(preArr[i] >= lower && preArr[i] <= uper){
                return 1;
            }
            return 0;
        }
        if(i < j){
            int middle = (i+j)/2;
            int res1 = split(preArr,i,middle,lower,uper);
            int res2 = split(preArr,middle+1,j,lower,uper);
            int res3 = merge(preArr,i,middle,middle+1,j,lower,uper);
            return res1+res2+res3;
        }
        return 0;
    }


    public static int merge(int [] preArr, int i1, int j1, int i2, int j2, int lower, int uper){

        int start1 = i1;
        int start2 = i2;
        int [] temp = new int[j2-i1+1];
        int tempIdx = 0;
        int res =0;

        // for(int m = i2;m<=j2;m++){
        //     for(int n=i1;n<=j1;n++){
        //         if(preArr[m] - preArr[n] >= lower && preArr[m] - preArr[n] <= uper){
        //             res++;
        //         }
        //         if(preArr[m] - preArr[n] < lower){
        //             //n 向右边移动 preArr[n] 只会越来越大
        //             n = j1;
        //         }
        //     }
        // }
        //使用滑动窗口 时间复杂度为O(N)
        //  3 4 5   6 7 8   [2,4]
        int L = i1;
        int R = i1;
        for(int m = i2;m<=j2;m++){
            int min = preArr[m] - uper;
            int max = preArr[m] - lower;
            //L R 开始向右边滑动，
            while(L <= j1 && preArr[L] <min){
                L++;
            }
            while(R <= j1 && preArr[R] <= max){
                R++;
            }
            int result = Math.max(0,R - L);//防止越界
            res+=result;
        }



        while(start1 <= j1 && start2 <= j2){

            if(preArr[start1] < preArr[start2]){
                temp[tempIdx++] = preArr[start1++];
            }else{
                temp[tempIdx++] = preArr[start2++];
            }
        }

        while(start1 <= j1){
            temp[tempIdx++] = preArr[start1++];
        }

        while(start2 <= j2){
            temp[tempIdx++] = preArr[start2++];
        }
        tempIdx = 0;
        for(int n = i1;n<=j2;n++){
            preArr[n] = temp[tempIdx++];
        }

        return res;
    }



    public static void main(String[] args) {

        int [] arr= {3,4,5,1,2};
        System.out.println(getNumFromRange(arr,3,5));
        System.out.println(getNumFromRange2(arr,3,5));
    }

}
